//https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/?envType=daily-question&envId=2023-11-10

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        int n = spells.size(), m = potions.size();
        vector<int> ans(n, 0);
        for(int i = 0; i < n; i++)
        {
            if((long long)spells[i] * (long long)potions[m - 1] < success) 
            {
                ans[i] = 0;
            }
            else
            {
                int left = 0, right = m - 1;
                while(left <= right)
                {
                    int tmp = (left + right) / 2;
                    if((long long)spells[i] * (long long)potions[tmp] >= success)
                    {
                        right = tmp - 1;
                    }
                    else
                    {
                        left = tmp + 1;
                    }
                }
                ans[i] = m - left;
            }
        }
        return ans;
    }
};